package primary.code05_Tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @author Yudi Wang
 * @date 2021/7/8 10:33
 * <p>
 * 求解二叉树的最大宽度
 */
public class Code03_MaxWidthOfBinaryTree {
    /**
     * 使用 Map 结构存储节点的层次
     *
     * @param root
     * @return
     */
    private static Integer getMaxWidthOfTreeWithMap(Node root) {
        if (root == null) {
            return 0;
        }
        Map<Node, Integer> nodeLevel = new HashMap<>(25);
        Integer maxWidth = Integer.MIN_VALUE;
        Integer curLevel = 0;
        Integer curLevelWidth = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        nodeLevel.put(root, 0);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            Integer curNodeLevel = nodeLevel.get(curNode);
            if (curLevel.equals(curNodeLevel)) {
                //计算当前层的宽度
                curLevelWidth++;
            } else {
                //已进入下一层的宽度计算
                maxWidth = Math.max(maxWidth, curLevelWidth);
                curLevel = curNodeLevel;
                curLevelWidth = 1;
            }
            if (curNode.left != null) {
                queue.add(curNode.left);
                nodeLevel.put(curNode.left, curNodeLevel + 1);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
                nodeLevel.put(curNode.right, curNodeLevel + 1);
            }
        }
        return maxWidth;
    }

    private static Integer getMaxWidthOfTreeWithMapTest(Node root) {
        if (root == null) return 0;
        int maxWidth = Integer.MIN_VALUE;
        int curLevel = 0;
        int curWidth = 0;
        Map<Node, Integer> NodeLevelMap = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        Node cur = root;
        NodeLevelMap.put(cur, 1);
        while (cur != null || !queue.isEmpty()) {
            Integer nodeLevel = NodeLevelMap.get(cur);
            if (nodeLevel != curLevel) {
                maxWidth = Math.max(maxWidth, curWidth);
                curLevel = nodeLevel;
                curWidth = 1;
            } else {
                curWidth++;
            }
            if (cur.left != null) {
                queue.offer(cur.left);
                NodeLevelMap.put(cur.left, curLevel + 1);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                NodeLevelMap.put(cur.right, curLevel + 1);
            }
            cur = queue.poll();
        }
        return maxWidth;
    }

    /**
     * 不使用 Map 结构记录节点的层次
     * 记录每层的最后一个节点
     *
     * @param root
     * @return
     */
    public static Integer getMaxWidthOfTreeWithoutMap(Node root) {
        if (root == null) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        //当前层最后的节点
        Node levelLastNode = root;
        //下层最后的节点
        Node nextLevelLastNode = null;
        queue.add(root);
        Integer maxWidth = Integer.MIN_VALUE;
        //当前层宽度
        Integer levelWidth = 0;
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();

            if (curNode.left != null) {
                queue.add(curNode.left);
                nextLevelLastNode = curNode.left;
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
                nextLevelLastNode = curNode.right;
            }
            //注意，处理本层结果的部分应该放在假如子节点之后
            if (curNode != levelLastNode) {
                //非本层最后的节点
                levelWidth++;
            } else {
                //本层最后的节点
                levelWidth++;
                maxWidth = Math.max(maxWidth, levelWidth);
                levelWidth = 0;
                levelLastNode = nextLevelLastNode;
                nextLevelLastNode = null;
            }
        }
        return maxWidth;
    }

    public static Integer getMaxWidthOfTreeWithoutMapTest(Node root) {
        if (root == null) {
            return 0;
        }
        Node curLast = root;
        Node nextLast = null;
        int curCnt = 0;
        int max = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.left != null) {
                queue.add(cur.left);
                nextLast = cur.left;
            }
            if (cur.right != null) {
                queue.add(cur.right);
                nextLast = cur.right;
            }
            curCnt++;
            if (cur == curLast) {
                // 结算
                max = Math.max(max, curCnt);
                curCnt = 0;
                curLast = nextLast;
                nextLast = null;
            }
        }
        return max;
    }


    public static void main(String[] args) {
        //构造树结构测试用
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        Node e = new Node(5);
        Node f = new Node(6);
        Node g = new Node(7);
        a.left = b;
        a.right = c;
        b.right = d;
        c.left = e;
        c.right = f;
        f.left = g;
        // 最大宽度：3
        Integer maxWidth1 = getMaxWidthOfTreeWithMap(a);
        System.out.println("with map, 最大宽度：" + maxWidth1);
        Integer maxWidth2 = getMaxWidthOfTreeWithMapTest(a);
        System.out.println("with map, test, 最大宽度：" + maxWidth2);
        Integer maxWidth3 = getMaxWidthOfTreeWithoutMap(a);
        System.out.println("without map,最大宽度：" + maxWidth3);
        Integer maxWidth4 = getMaxWidthOfTreeWithoutMapTest(a);
        System.out.println("without map, test, 最大宽度：" + maxWidth4);
    }
}
